package com.itheima.seach;

public class BlockSearch2 {
    public static void main(String[] args) {
        //分块查找扩展（无规律的数据）
        //关键点：分块之后，各块之间的数据范围不能有交集

        int[] arr = {27, 22, 30, 40, 36,
                13, 19, 16, 20,
                7, 10,
                43, 50, 48};
        Block1 b1 = new Block1(22, 40, 0, 4);
        Block1 b2 = new Block1(13, 20, 5, 8);
        Block1 b3 = new Block1(7, 10, 9, 10);
        Block1 b4 = new Block1(43, 50, 10, 12);

        int number = 51;
        Block1[] block1Arr = {b1, b2, b3, b4};

        int index= getIndex(arr, block1Arr, number);
        System.out.println(index);
    }

    private static int getIndex(int[] arr, Block1[] block1Arr, int number) {
        int block1Index = getBlock1Index(block1Arr, number);
        if (block1Index==-1){
            return -1;
        }
        Block1 b = block1Arr[block1Index];
        int startIndex = b.getStartIndex();
        int endIndex = b.getEndIndex();
        for (int i = startIndex; i <= endIndex; i++) {
            if(number==arr[i]){
                return i;
            }
        }
        return -1;
    }

    private static int getBlock1Index(Block1[] block1Arr, int number) {
        for (int i = 0; i < block1Arr.length; i++) {
            Block1 b = block1Arr[i];
            int min = b.getMin();
            int max = b.getMax();
            if (min<=number&&number<=max)
            {
                return i;
            }
        }
        return -1;
    }
}

class Block1 {
    private int min;
    private int max;
    private int startIndex;
    private int endIndex;


    public Block1() {
    }

    public Block1(int min, int max, int startIndex, int endIndex) {
        this.min = min;
        this.max = max;
        this.startIndex = startIndex;
        this.endIndex = endIndex;
    }

    /**
     * 获取
     *
     * @return min
     */
    public int getMin() {
        return min;
    }

    /**
     * 设置
     *
     * @param min
     */
    public void setMin(int min) {
        this.min = min;
    }

    /**
     * 获取
     *
     * @return max
     */
    public int getMax() {
        return max;
    }

    /**
     * 设置
     *
     * @param max
     */
    public void setMax(int max) {
        this.max = max;
    }

    /**
     * 获取
     *
     * @return startIndex
     */
    public int getStartIndex() {
        return startIndex;
    }

    /**
     * 设置
     *
     * @param startIndex
     */
    public void setStartIndex(int startIndex) {
        this.startIndex = startIndex;
    }

    /**
     * 获取
     *
     * @return endIndex
     */
    public int getEndIndex() {
        return endIndex;
    }

    /**
     * 设置
     *
     * @param endIndex
     */
    public void setEndIndex(int endIndex) {
        this.endIndex = endIndex;
    }

    public String toString() {
        return "Block1{min = " + min + ", max = " + max + ", startIndex = " + startIndex + ", endIndex = " + endIndex + "}";
    }
}
